package com.jdaw.datastructure.sort;

import java.util.Arrays;

public class HeapSort {
    public static void main(String[] args) {
        int[] arr={4,6,8,5,9};
        heapSort(arr);
    }

    public static void heapSort(int[] arr){
        int temp=0;
        for(int i=arr.length/2-1;i>=0;i--){
            adjustHeap(arr,i, arr.length);
        }

        for(int j=arr.length-1;j>=0;j--){
            temp=arr[j];
            arr[j]=arr[0];
            arr[0]=temp;
            adjustHeap(arr,0,j);
        }
        System.out.println(Arrays.toString(arr));
    }

    //数组构建为大顶堆,i表示非叶子节点的下标,length表示对多少个元素进行调整
    public static void adjustHeap(int[] arr,int i,int length){
        int temp=arr[i];
        for(int k=2*i+1;k<length;k=2*k+1){
            if(k+1<length&&arr[k]<arr[k+1]){//说明左子节点小于右子节点
                k++;//让k指向右子节点
            }
            if(arr[k]>temp){
                arr[i]=arr[k];//把较大的值赋给当前节点
                i=k;
            }else{
                break;
            }
        }
        arr[i]=temp;
    }
}
